package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Q797 {

    /**
     * @param target: the destination
     * @return: the minimum number of steps
     */
    public int reachNumber(int target) {
//        // Write your code here
//    	if(target == 0) {
//    		return 0;
//    	}
//    	Set<Integer> set = new HashSet<>();
//    	int n = 1;
//    	set.add(0);
//    	a: while(!set.isEmpty()) {
//    		Set<Integer> tmp = new HashSet<>();
//    		for(int i : set) {
//    			int t = i + n;
//    			if(t == target) {
//    				break a;
//    			}
//    			tmp.add(t);
//    			t = i - n;
//    			if(t == target) {
//    				break a;
//    			}
//    			tmp.add(t);
//    		}
//    		n++;
//    		set = tmp;
//    	}
//    	return n;

        target = Math.abs(target);
        int res = 0, sum = 0;
        while (sum < target || (sum - target) % 2 == 1) {
            ++res;
            sum += res;
        }
        return res;
    }

}
